package bm5;

import java.util.ArrayList;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/7/20 0:19
 * BM5.合并 k 个已排序的链表
 * https://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6?tpId=295&tqId=724&ru=%2Fpractice%2Fd8b6b4358f774294a89de2a6ac4d9337&qru=%2Fta%2Fformat-top101%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj
 */
public class Solution {

    // 方法1: 两两迭代
    public ListNode mergeKLists01 (ArrayList<ListNode> lists) {
        // 边界处理
        if (lists == null || lists.size() == 0) {
            return null;
        }
        // 遍历 k 个有序链表, 两两合并
        ListNode head = lists.get(0);
        for (int i = 1; i < lists.size(); i++) {
            head = Merge(head, lists.get(i));
        }
        return head;
    }

    // 方法2: 分治思想
    public ListNode mergeKLists02 (ArrayList<ListNode> lists) {
        //k个链表归并排序
        return divideMerge(lists, 0, lists.size() - 1);
    }

    // 划分合并区间
    private ListNode divideMerge(ArrayList<ListNode> lists, int left, int right) {
        if(left > right)
            return null;
        // 中间一个的情况
        else if(left == right)
            return lists.get(left);
        // 从中间分成两段，再将合并好的两段合并
        int mid = (left + right) / 2;
        return Merge(divideMerge(lists, left, mid), divideMerge(lists, mid + 1, right));
    }

    // 合并两个有序链表
    public ListNode Merge (ListNode pHead1, ListNode pHead2) {
        // 构造哑巴节点, 最终返回的结果为 muteNode.next
        ListNode muteNode = new ListNode(-1);
        // 构造辅助指针
        ListNode curA = pHead1;
        ListNode curB = pHead2;
        ListNode cur = muteNode;
        // 合并过程
        while (curA != null && curB != null) {
            if (curA.val <= curB.val) {
                cur.next = curA;
                curA = curA.next;
            } else {
                cur.next = curB;
                curB = curB.next;
            }
            cur = cur.next;
        }
        // 处理剩余的部分
        if (curA != null) {
            cur.next = curA;
        }
        if (curB != null) {
            cur.next = curB;
        }
        return muteNode.next;
    }

    private static class ListNode {
        int val;
        ListNode next = null;
        public ListNode(int val) {
            this.val = val;
        }
    }
}
